package com.spirng.leetcode.day08;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test131 {
    public static void main(String[] args) {
        Test131 test131 = new Test131();
        List<List<String>> aab = test131.partition("aab");

    }
    ArrayList lists=new ArrayList<List<String>>();
    LinkedList list=new LinkedList<String>();
    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return  lists;
    }
    public void backtracking(String s,int startSize){
        if(startSize>=s.length()){
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = startSize; i < s.length(); i++) {

                if(Manacher(s,startSize,i)){
                    String str=s.substring(startSize,i+1);
                    list.add(str);
                }else {
                    continue;
                }
                backtracking(s,i+1);
                list.removeLast();
        }
    }
    public Boolean Manacher(String s,int start,int end){
        char[] array = s.toCharArray();
        for (int i = start,j=end; i <j ; i++,j--) {
            if(array[i]!=array[j]){
                return false;
            }
        }
        return true;
    }

}
